We first show that the estimate is unbiased. Next, we turn to analyze the variance of the multibatch estimate.

Major comments: 1) This reviewer's main concern is that although impressive performance on the LFW protocol is showcased in a very competitive setting, a atleast one or two more databases might be required to demonstrate that the protocol can scale up. Given that the practical contribution is primarily in terms of training through multibatch, more empirical evidence might be required. This reviewer imagines the results would generalize to other datasets, but given the strong focus of the paper on face recognition specifically, perhaps one or two more dataset results might be needed. This is the only major reason for the score of 2 on technical quality. The final architecture employs a Network in network model, however given the fact that the paper aims to minimize model and computational complexity, it is a bit confusing (perhaps I m missing something) as to why the final model still seems more complex than a standard CNN.

This work is motivated by the engineering task of achieving a near state-of-the-art face recognition on a minimal computing budget running on an embedded system. Our main technical contribution centers around a novel training method, called Multibatch, for similarity learning, i.e., for the task of generating an invariant face signature'' through training pairs of same'' and not-same'' face images. The Multibatch method first generates signatures for a mini-batch of $k$ face images and then constructs an unbiased estimate of the full gradient by relying on all $k 2-k$ pairs from the mini-batch. We prove that the variance of the Multibatch estimator is bounded by $O(1/k 2)$, under some mild conditions. In contrast, the standard gradient estimator that relies on random $k/2$ pairs has a variance of order $1/k$. The smaller variance of the Multibatch estimator significantly speeds up the convergence rate of stochastic gradient descent.

This work is motivated by the engineering task of achieving a near state-of-the-art face recognition on a minimal computing budget running on an embedded system. Our main technical contribution centers around a novel training method, called Multibatch, for similarity learning, i.e., for the task of generating an invariant ``face signature'' through training pairs of ``same'' and ``not-same'' face images. The Multibatch method first generates signatures for a mini-batch of $k$ face images and then constructs an unbiased estimate of the full gradient by relying on all $k^2-k$ pairs from the mini-batch. We prove that the variance of the Multibatch estimator is bounded by $O(1/k^2)$, under some mild conditions. In contrast, the standard gradient estimator that relies on random $k/2$ pairs has a variance of order $1/k$. The smaller variance of the Multibatch estimator significantly speeds up the convergence rate of stochastic gradient descent. Using the Multibatch method we train a deep convolutional neural network that achieves an accuracy of $98.2\%$ on the LFW benchmark, while its prediction runtime takes only $30$msec on a single ARM Cortex A9 core. Furthermore, the entire training process took only 12 hours on a single Titan X GPU.